package binarySearch;

/**
 * @author pengfei.hpf
 * @date 2020/2/19
 * @verdion 1.0.0
 * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 *
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 *
 * 示例 1:
 *
 * 输入: dividend = 10, divisor = 3
 * 输出: 3
 * 示例 2:
 *
 * 输入: dividend = 7, divisor = -3
 * 输出: -2
 * 说明:
 *
 * 被除数和除数均为 32 位有符号整数。
 * 除数不为 0。
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/divide-two-integers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class DivideTwoIntegers {

    public int divide(int dividend, int divisor){
        if(dividend == 0){
            return 0;
        }
        if(divisor == 1){
            return dividend;
        }
        int flag = 1;
        if((dividend > 0 && divisor <0) || (dividend <0 && divisor > 0)){
            flag = -1;
        }
        //TODO: 注意在int INTEGER.MIN_VALUE转正数的时候 会溢出
        long a = dividend > 0? (long)dividend: 0-(long)dividend;
        long b = divisor > 0? (long)divisor: 0-(long)divisor;
        long count = div(a, b);
        int res = 0;
        if(flag == 1){
            if(count > Integer.MAX_VALUE){
                res = Integer.MAX_VALUE;
            } else {
                res += count;
            }
        } else {
            res -= count;
        }
        return res;
    }

    private long div(long a, long b){
        if(a < b){
            return 0;
        }
        long tb = b;
        long count = 1;
        while(a >= tb + tb){
            count += count;
            tb += tb;
        }
        a = a -  tb;
        return count + div(a, b);
    }
}
